package psn.zjk.career.interview.algorithm;


import java.util.HashMap;
import java.util.HashSet;

/**
 * @Description 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * @User zero
 * @Datetime 2021/5/10 8:09
 */
public class LeetCode3 {

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int index = 0;
        HashMap<String, Integer> map = new HashMap<>();
        String[] split = s.split("");
        int length = s.length();
        int max = 0;
        while (index < length) {
            for (int i = index; i < split.length; i++) {
                if (!map.containsKey(split[i])) {
                    map.put(split[i], index);
                    if (i + 1 == split.length) {
                        //没有重复的情况
                        max = Math.max(max, split.length - index);
                    }
                } else {//存在重复的情况
                    max = Math.max(max, i - index);
                    //下一个子串的起始索引=重复字符所在索引+1
                    index = map.get(split[i]) + 1;
                    map.clear();
                    break;
                }
            }
        }
        return max;
    }

    /** 双指针法 */
    public int lengthOfLongestSubstring2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int right = 0, max = 0, length = s.length();
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            //左指针前进一格，移除一个
            if (i != 0) {
                set.remove(s.charAt(i - 1));
            }
            //只要未越界、下一个字符不重复，右指针就右移
            while (right + 1 < length && !set.contains(s.charAt(right + 1))) {
                right++;
                set.add(s.charAt(right));
            }
            max = Math.max(max, set.size());
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode3().lengthOfLongestSubstring("abcabcbb"));
    }

}
